package _05_二叉树;

import java.util.LinkedList;

public class _116_填充每个节点的下一个右侧节点指针 {

    // 二叉树，递归
    public Node connect(Node root) {
        if (root == null) return root;
        if (root.left != null) {
            root.left.next = root.right;
            if (root.next != null) {
                root.right.next = root.next.left;
            }
            connect(root.left);
            connect(root.right);
        }
        return root;
    }

    // 层序遍历，非递归
    public Node connect1(Node root) {
        if (root == null) return root;
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.offer(root);
        while (!nodes.isEmpty()) {
            Node node = nodes.poll();
            if (node.left == null) continue;
            node.left.next = node.right;
            nodes.offer(node.left);
            if (node.next != null) {
                node.right.next = node.next.left;
            }
            nodes.offer(node.right);
        }
        return root;
    }
}
